Packet-switched networks are responsible for forwarding packet-based traffic. When a large amount of traffic is forwarded through the network, the network can become congested. When a network is congested, queues within the network have a relatively large number of packets enqueued in them. If the congestion is not alleviated, the queues fill up and subsequent incoming packets must be dropped. This typically results in a high proportion of packets from the same source being dropped. Also, the congestion itself can slow the network down. There are a number of techniques to avoid network congestion. One such technique is random early drop (RED). RED gateways are designed to accompany a transport-layer congestion control protocol such as transmission control protocol (TCP). RED logic within the RED gateways is typically designed to provide congestion avoidance by controlling average queue size, but may also be designed to avoid global synchronization, avoid a bias against bursty traffic, and maintain an upper bound on the average queue size. RED logic reacts to incipient congestion either by dropping packets that are arriving at a queue or by setting a bit in packet headers. The RED logic helps keep the average queue size manageable, which keeps average delay in the network manageable, while allowing occasional bursts of packets in the queue so as to avoid a bias against bursty traffic.
A RED algorithm calculates average queue size using a low-pass filter with an exponential weighted moving average. The average queue size is compared to two thresholds, a minimum threshold and a maximum threshold. When the average queue size is less than the minimum threshold, no packets are marked. When the average queue size is greater than the maximum queue size, every packet is marked. If marked packets are dropped, the average queue size should not significantly exceed the maximum threshold. When the average queue size is between the minimum threshold and the maximum threshold, arriving packets are marked with a probability that is a function of the average queue size. Thus, the RED algorithm actually consists of two algorithms, a first for computing the average queue size determines the degree of burstiness that will be allowed, and a second for calculating packet-marking probability determines how frequently the gateway marks packets for a given level of congestion. The goal is to mark packets at fairly evenly-spaced intervals, in order to avoid biases and to avoid global synchronization, and to mark packets sufficiently frequently to control the average queue size.
FIGS. 1A and 1B demonstrate the treatment of packets in accordance with a RED algorithm. In graph 100A, packets are dropped with a probability that is based upon which of three zones a packet is in. The first zone is below a minimum threshold, minth; the second zone is above a maximum threshold, maxth; and the third zone is between minth and maxth, in what is sometimes referred to as the RED zone. The plot 110 illustrates the likelihood of a drop for a packet in any of the three zones. In the first zone, a packet has a 0 probability of being dropped. In the second zone, the probability is 1 (i.e., all packets are dropped). In the third zone, packets have a probability that is a function of the average size of the queue. The system 100B illustrates the three zones with respect to a queue 104. The queue 104 is divided into three zones comparable to the three zones of the graph 100A.
Formula 1, below, is a typical algorithm for calculating the average queue size. Formulae (2a), (2b), and (2c) are, together, a typical algorithm for calculating the probability of drop for a packet. The formulae are as follows:avg←avg+(qsize−avg)*wq  (1)A=maxp(avg−minth)/(maxth−minth)  (2a)B=A(Packet Size/Max Packet Size)  (2b)Probability of Drop=B/(1−(Count*B))  (2c)where:                avg=average queue size,        qsize=the real queue size,        wq=the weight of the queue,        minth=minimum queue size threshold,        maxth=maximum queue size threshold,        maxp=packet marking probability, and        Count=number of accepted cells since last drop.        
The variables of the formulae are absolute numbers in that they do not vary with packet-based parameters. However, it may be desirable to afford different treatment for certain packets, such as those having an assured forwarding (AF) class, which is a differentiated service (DS) per-hop-behavior (PHB) group. For further information on the AF PHB group, see Heinanen, Request for Comments (RFC) 2597, June 1999, which is incorporated herein by reference as background. Nichols et al., RFC 2474, December 1998, incorporated herein by reference as background, defines the DS Internet protocol (IP) header field, and Blake et al., RFC 2475, December 1998, incorporated herein by reference as background, defines a DS architecture. The standard RED algorithm does not differentiate between packets with different traffic classes. However, there is a need for IP packets to be assigned different drop precedence based on traffic class. Accordingly, there is a need for a modified RED algorithm that differentiates between packets of differing traffic classes. The algorithm should be implementable in a high-speed switched network in accordance with AF PHB group requirements.
In view of the desire to provide PHB bias to a RED algorithm, what is needed is a new RED algorithm that includes per-packet adjustments to a modified RED algorithm, so that packets with different traffic classes are treated differently within a queue. It would be advantageous to include guaranteed and dynamic resource allocation for certain traffic classes.